package 中等.动态规划.子序列;

/**
 * 把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：
 * "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 
 * 现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string
 */
public class 环绕字符串中唯一的子字符串_467 {

    public static void main(String[] args) {

        System.out.println(findSubstringInWraproundString("zaba"));

    }

    /**
     * 统计在p中以 字母 dp[i] 结尾的最长连续子数组
     * <p>
     * 例如在 p 中 ，如果 p[i]-p[i-1]=1 ,或者是 'a'-'z' 那么
     * 那么 p[i] 字符结尾的最长长度 是 p[i-1] + 1,
     * 否则 就是 1
     *
     * @param p
     * @return
     */
    public static int findSubstringInWraproundString(String p) {
        int[] dp = new int[26];
        char[] pChars = p.toCharArray();
        dp[pChars[0] - 'a'] = 1;
        int preCount = 1;
        for (int i = 1; i < pChars.length; i++) {
            char curChar = pChars[i];
            char preChar = pChars[i - 1];
            if (curChar - preChar == 1 || curChar - preChar == -25) {
                dp[curChar - 'a'] = Math.max(dp[curChar - 'a'], ++preCount);
            } else {
                dp[curChar - 'a'] = Math.max(dp[curChar - 'a'], 1);
                preCount = 1;
            }
        }
        int sum = 0;
        for (int count : dp) {
            sum += count;
        }
        return sum;
    }

}
